package basic.class2;

/**
 * 栈解决
 * https://leetcode.cn/problems/valid-parentheses/
 * 有效的括号
 */
public class Code01_isValid {
    public static void main(String[] args) {
        String str = "[(()]}";
        boolean valid = isValid(str);
        System.out.println("valid = " + valid);
    }

    public static boolean isValid(String str) {
        int r = 0, n = str.length();
        if (n % 2 != 0) {
            return false;
        }
        char[] stack = new char[n];
        char[] chars = str.toCharArray();

        for (char c : chars) {
            // 当遇到开始括号时，直接进栈
            if ('(' == c || '[' == c || '{' == c) {
                stack[r++] = c;
            } else {
                // 当遇结尾括号时，到出栈时，
                if (r == 0) {
                    return false;
                }
                char pop = stack[--r];
                // 当出栈的符合与结尾字符不同时，返回false
                if (pop == '[' && c != ']' || pop == '(' && c != ')' || pop == '{' && c != '}') {
                    return false;
                }
            }
        }
        return r == 0;
    }
}
